//给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。 
//
// 百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（
//一个节点也可以是它自己的祖先）。” 
//
// 例如，给定如下二叉搜索树: root = [6,2,8,0,4,7,9,null,null,3,5] 
//
// 
//
// 
//
// 示例 1: 
//
// 输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8
//输出: 6 
//解释: 节点 2 和节点 8 的最近公共祖先是 6。
// 
//
// 示例 2: 
//
// 输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4
//输出: 2
//解释: 节点 2 和节点 4 的最近公共祖先是 2, 因为根据定义最近公共祖先节点可以为节点本身。 
//
// 
//
// 说明: 
//
// 
// 所有节点的值都是唯一的。 
// p、q 为不同节点且均存在于给定的二叉搜索树中。 
// 
// Related Topics 树 
// 👍 598 👎 0

package leetcode.editor.cn;

import common.bean.TreeNode;

/**
 * Java：二叉搜索树的最近公共祖先
 *
 * @author changgui
 */
@SuppressWarnings("all")
public class P235_LowestCommonAncestorOfABinarySearchTree {
    public static void main(String[] args) {
        Solution solution = new P235_LowestCommonAncestorOfABinarySearchTree().new Solution();
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
            return process(root, p, q).ancestor;
        }

        Info process(TreeNode node, TreeNode a, TreeNode b) {
            if (node == null) {
                return new Info(false, false, null);
            }
            Info li = process(node.left, a, b);
            Info ri = process(node.right, a, b);
            boolean findA = node == a || li.findA || ri.findA;
            boolean findB = node == b || li.findB || ri.findB;
            TreeNode ans = null;
            if (li.ancestor != null) {
                ans = li.ancestor;
            } else if (ri.ancestor != null) {
                ans = ri.ancestor;
            } else if (findA && findB) {
                ans = node;
            }

            return new Info(findA, findB, ans);
        }

        class Info {
            boolean findA;
            boolean findB;
            TreeNode ancestor;

            public Info(boolean findA, boolean findB, TreeNode ancestor) {
                this.findA = findA;
                this.findB = findB;
                this.ancestor = ancestor;
            }
        }
    }
    //leetcode submit region end(Prohibit modification and deletion)

}